'''
https://blog.csdn.net/XianZhe_/article/details/114962984
背包法 求最优解，
每个物品只能取一次，
需要能输出最大价值，以及最大价值的组合
'''


def dynamic_p() -> list:
    '''不能重复拿物品的情况'''
    items = [  									 # 物品项
        {"name": "水", "weight": 3, "value": 10},
        {"name": "书", "weight": 1, "value": 3},
        {"name": "食物", "weight": 2, "value": 9},
        {"name": "小刀", "weight": 3, "value": 4},
        {"name": "衣物", "weight": 2, "value": 5},
        {"name": "手机", "weight": 1, "value": 10}
    ]
    max_capacity = 6                             # 约束条件为 背包最大承重为6
    dp = [[0] * (max_capacity + 1) for _ in range(len(items) + 1)]

    '''建立一个字典，用于存放每一步的物品组合，坐标与dp相对应'''
    res_dict = {}
    for i in range(len(items) + 1): # 行为物品的类型数目
        for j in range(max_capacity + 1): # 列为约束条件的大小
            res_dict["[{0}][{1}]".format(i, j)] = [""]

    for row in range(1, len(items) + 1):         # row 代表行
        for col in range(1, max_capacity + 1):   # col 代表列
            weight = items[row - 1]["weight"]    # 获取当前物品重量
            value = items[row - 1]["value"]      # 获取当前物品价值

            if weight > col:                     # 判断物品重量是否大于当前背包容量
                dp[row][col] = dp[row - 1][col]  # 大于直接取上一次最优结果 此时row-1代表上一行
                res_dict["[{0}][{1}]".format(row, col)] = res_dict["[{0}][{1}]".format(row - 1, col)]
            else:
                # 使用内置函数max()，将上一次最优结果 与 当前物品价值+剩余空间可利用价值 做对比取最大值
                # dp[row][col] = max(value + dp[row - 1][col - weight], dp[row - 1][col]) # 否则就进行状态交换
                if value + dp[row - 1][col - weight] > dp[row - 1][col]:
                    # 价值增大但没有超出背包容量，就把总价值加起来，并把涉及到组合类型合并起来
                    dp[row][col] = value + dp[row - 1][col - weight]
                    # 这里的字典里物品的类型是以倒序存放的，所以若果题目有要求正序，在返回时倒过来即可[::-1]
                    res_dict["[{0}][{1}]".format(row, col)].append(items[row - 1]["name"])
                    res_dict["[{0}][{1}]".format(row, col)] += res_dict["[{0}][{1}]".format(row - 1, col - weight)]
                else:
                    dp[row][col] = dp[row - 1][col]
                    res_dict["[{0}][{1}]".format(row, col)] = res_dict["[{0}][{1}]".format(row - 1, col)]
    # print(res_dict["[{0}][{1}]".format(len(items), max_capacity)]) # 若题目需要可去除空字符
    res_comb = []
    for i in res_dict["[{0}][{1}]".format(len(items), max_capacity)]:
        if i != '':
            res_comb.append(i)
    # res_comb = res_comb[::-1] # 把顺序倒回来
    return dp, res_comb


dp, res_comb = dynamic_p()
for i in dp:                                     # 打印数组
    print(i)
print(dp[-1][-1])                                # 打印最优解的价值和
print(res_comb)



def dynamic_p02() -> list:
    '''可重复拿取的情况'''
    items = [  									 # 物品项
        {"name": "水", "weight": 3, "value": 10},
        {"name": "书", "weight": 1, "value": 3},
        {"name": "食物", "weight": 2, "value": 9},
        {"name": "小刀", "weight": 3, "value": 4},
        {"name": "衣物", "weight": 2, "value": 5},
        {"name": "手机", "weight": 1, "value": 10}
    ]
    max_capacity = 6                             # 约束条件为 背包最大承重为6
    dp = [[0] * (max_capacity + 1) for _ in range(len(items) + 1)]

    for row in range(1, len(items) + 1):         # row 代表行
        for col in range(1, max_capacity + 1):   # col 代表列
            weight = items[row - 1]["weight"]    # 获取当前物品重量
            value = items[row - 1]["value"]      # 获取当前物品价值
            if weight > col:                     # 判断物品重量是否大于当前背包容量
                dp[row][col] = dp[row - 1][col]  # 大于直接取上一次最优结果 此时row-1代表上一行
            else:
                # row-1 为上一行，row为本行，若要重复拿取，只需要在目前物品所在的那一行寻找最优解即可
                dp[row][col] = max(value + dp[row][col - weight], dp[row - 1][col])  # 只有这里的dp[row]与上面不同
    return dp


dp = dynamic_p02()
for i in dp:                                     # 打印数组
    print(i)

print(dp[-1][-1])                                # 打印最优解的价值和









